SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Circular shift</title>

</head>

Circular shift

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:392px;max-width:392px"><div class="trow"><div class="tsingle" style="width:194px;max-width:194px"><div class="thumbimage" style="height:168px;overflow:hidden"></div></div><div class="tsingle" style="width:194px;max-width:194px"><div class="thumbimage" style="height:168px;overflow:hidden"></div></div></div><div class="trow" style="display:flex"><div class="thumbcaption"><a href="Permutation_matrix" title="Permutation matrix">Matrices</a> of 8-element circular shifts to the left and right</div></div></div></div>

In <a href="Combinatorics" title="Combinatorics">combinatorial</a> <a href="Mathematics" title="Mathematics">mathematics</a>, a circular shift is the operation of rearranging the entries in a <a href="Tuple" title="Tuple">tuple</a>, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of <a href="Cyclic_permutation" title="Cyclic permutation">cyclic permutation</a>, which in turn is a special kind of <a href="Permutation" title="Permutation">permutation</a>. Formally, a circular shift is a <a href="Permutation" title="Permutation">permutation</a> σ of the n entries in the tuple such that either

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma (i)\equiv (i+1)}</annotation>

</semantics>

</math><img src="./f3d1fbdd6372c22119032adf0398c6c172f8e739.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.655ex; height:2.843ex;" alt="{\displaystyle \sigma (i)\equiv (i+1)}" loading="lazy"> <a href="Modular_arithmetic" title="Modular arithmetic">modulo</a> n, for all entries i = 1, ..., n</dd></dl>

or

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma (i)\equiv (i-1)}</annotation>

</semantics>

</math><img src="./a65139cfef5b7267f19ee66727ff676f37308ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.655ex; height:2.843ex;" alt="{\displaystyle \sigma (i)\equiv (i-1)}" loading="lazy"> <a href="Modular_arithmetic" title="Modular arithmetic">modulo</a> n, for all entries i = 1, ..., n.</dd></dl>

The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple.

For example, repeatedly applying circular shifts to the four-tuple (a, b, c, d) successively gives

<li>(a, b, c, d) (the original four-tuple),</li></ul>

and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all n-tuples have n distinct circular shifts. For instance, the 4-tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n-tuple is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{k}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{k}}}</annotation>

</semantics>

</math><img src="./a3de84bab054ffbe095b1f1d9422876cc3a1d7ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:2.231ex; height:4.843ex;" alt="{\displaystyle {\frac {n}{k}}}" loading="lazy">, where k is a <a href="Divisor" title="Divisor">divisor</a> of n, indicating the maximal number of repeats over all subpatterns.

In <a href="Computer_programming" title="Computer programming">computer programming</a>, a <a href="Bitwise_rotation" class="mw-redirect" title="Bitwise rotation">bitwise rotation</a>, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an <a href="Arithmetic_shift" title="Arithmetic shift">arithmetic shift</a>, a circular shift does not preserve a number's sign bit or distinguish a <a href="Floating-point_number" class="mw-redirect" title="Floating-point number">floating-point number</a>'s <a href="Exponent" class="mw-redirect" title="Exponent">exponent</a> from its <a href="Significand" title="Significand">significand</a>. Unlike a <a href="Logical_shift" title="Logical shift">logical shift</a>, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.

<div class="mw-heading mw-heading2"><h2 id="Implementing_circular_shifts">Implementing circular shifts</h2></div>

Circular shifts are used often in <a href="Cryptography" title="Cryptography">cryptography</a> in order to permute bit sequences. Unfortunately, many programming languages, including <a href="C_(programming_language)" title="C (programming language)">C</a>, do not have operators or standard functions for circular shifting, even though virtually all <a href="Processor_(computing)" title="Processor (computing)">processors</a> have <a href="Bitwise_operation" title="Bitwise operation">bitwise operation</a> instructions for it (e.g. <a href="Intel_x86" class="mw-redirect" title="Intel x86">Intel x86</a> has ROL and ROR).

However, some compilers may provide access to the processor instructions by means of <a href="Intrinsic_function" title="Intrinsic function">intrinsic functions</a>. In addition, some constructs in standard <a href="ANSI_C" title="ANSI C">ANSI C</a> code may be optimized by a compiler to the "rotate" assembly language instruction on CPUs that have such an instruction. Most C compilers recognize the following idiom, and compile it to a single 32-bit rotate instruction.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>/*

* Shift operations in C are only defined for shift values which are

* not negative and smaller than sizeof(value) * CHAR_BIT.

* The mask, used with bitwise-and (&), prevents undefined behaviour

* when the shift count is 0 or >= the width of unsigned int.

*/

#include <stdint.h> // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.

#include <limits.h> // for CHAR_BIT

uint32_t rotl32 (uint32_t value, unsigned int count) {

const unsigned int mask = CHAR_BIT * sizeof(value) - 1;

count &= mask;

return (value << count) | (value >> (-count & mask));

}

uint32_t rotr32 (uint32_t value, unsigned int count) {

count &= mask;

return (value >> count) | (value << (-count & mask));

}

</pre></div>

This safe and compiler-friendly implementation was developed by <a href="John_Regehr" title="John Regehr">John Regehr</a>,<a href="#cite_note-3">[3]</a> and further polished by Peter Cordes.<a href="#cite_note-4">[4]</a><a href="#cite_note-5">[5]</a>

A simpler version is often seen when the <code>count</code> is limited to the range of 1 to 31 bits:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>uint32_t rotl32 (uint32_t value, unsigned int count) {

return (value << count) | (value >> (32 - count));

}

</pre></div>

This version is dangerous because if the <code>count</code> is 0 or 32, it asks for a 32-bit shift, which is <a href="Undefined_behaviour" class="mw-redirect" title="Undefined behaviour">undefined behaviour</a> in the C language standard. However, it tends to work anyway, because most microprocessors implement <code>value >> 32</code> as either a 32-bit shift (producing 0) or a 0-bit shift (producing the original <code>value</code>), and either one produces the correct result in this application.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

If the bit sequence 0001 0111 were subjected to a circular shift of one bit position... (see images below)

<table>

<td>

<ul><li>to the left would yield: 0010 1110</li></ul>

</td>

<td>

<ul><li>to the right would yield: 1000 1011.</li></ul>

</td></tr></tbody></table>

If the bit sequence 1001 0110 were subjected to the following operations:

<td>left circular shift by 1 position:

</td>

<td>0010 1101

</td></tr>

<tr>

<td>left circular shift by 2 positions:

</td>

<td>0101 1010

</td></tr>

<tr>

<td>left circular shift by 3 positions:

</td>

<td>1011 0100

</td></tr>

<tr>

<td>left circular shift by 4 positions:

</td>

<td>0110 1001

</td></tr>

<tr>

<td>left circular shift by 5 positions:

</td>

<td>1101 0010

</td></tr>

<tr>

<td>left circular shift by 6 positions:

</td>

<td>1010 0101

</td></tr>

<tr>

<td>left circular shift by 7 positions:

</td>

<td>0100 1011

</td></tr>

<tr>

<td>left circular shift by 8 positions:

</td>

<td>1001 0110

</td></tr></tbody></table>

<td>right circular shift by 1 position:

</td>

<td>0100 1011

</td></tr>

<tr>

<td>right circular shift by 2 positions:

</td>

<td>1010 0101

</td></tr>

<tr>

<td>right circular shift by 3 positions:

</td>

<td>1101 0010

</td></tr>

<tr>

<td>right circular shift by 4 positions:

</td>

<td>0110 1001

</td></tr>

<tr>

<td>right circular shift by 5 positions:

</td>

<td>1011 0100

</td></tr>

<tr>

<td>right circular shift by 6 positions:

</td>

<td>0101 1010

</td></tr>

<tr>

<td>right circular shift by 7 positions:

</td>

<td>0010 1101

</td></tr>

<tr>

<td>right circular shift by 8 positions:

</td>

<td>1001 0110

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<a href="Cyclic_code" title="Cyclic code">Cyclic codes</a> are a kind of <a href="Block_code" title="Block code">block code</a> with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a <a href="String_(computer_science)" title="String (computer science)">string</a> s over an alphabet Σ, let shift(s) denote the <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of circular shifts of s,

and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a <a href="Cyclic_language" title="Cyclic language">cyclic language</a>. The operation shift(L) has been studied in <a href="Formal_language_theory" class="mw-redirect" title="Formal language theory">formal language theory</a>. For instance, if L is a <a href="Context-free_language" title="Context-free language">context-free language</a>, then shift(L) is again context-free.<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a> Also, if L is described by a <a href="Regular_expression" title="Regular expression">regular expression</a> of length n, there is a regular expression of length <a href="Big_O_notation" title="Big O notation">O</a>(n3) describing shift(L).<a href="#cite_note-8">[8]</a>

<ul><li><a href="Barrel_shifter" title="Barrel shifter">Barrel shifter</a></li>

<li><a href="Circulant" class="mw-redirect" title="Circulant">Circulant</a></li>

<li><a href="Lyndon_word" title="Lyndon word">Lyndon word</a></li>

<li><a href="Necklace_(combinatorics)" title="Necklace (combinatorics)">Necklace</a> — an object like a <a href="Tuple" title="Tuple">tuple</a> but for which circular shifts are considered equivalent.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<a rel="nofollow" class="external text" href="https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html">GCC: "Optimize common rotate constructs"</a>

</li>

<a rel="nofollow" class="external text" href="http://www.mail-archive.com/llvm-commits@cs.uiuc.edu/msg17216.html">"Cleanups in ROTL/ROTR DAG combiner code"</a> mentions that this code supports the "rotate" instruction in the CellSPU

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a rel="nofollow" class="external text" href="http://blog.regehr.org/archives/1063">Safe, Efficient, and Portable Rotate in C/C++</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a rel="nofollow" class="external text" href="https://stackoverflow.com/a/776523/224132">Stackoverflow: Best practices for rotates in C/C++</a>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a rel="nofollow" class="external text" href="https://stackoverflow.com/a/31488147/224132">Near constant time rotate that does not violate the standards</a>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, 55D:119–122, 1972.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission 9:333–338, 1973.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGruberHolzer2009" class="citation journal cs1">Gruber, Hermann; Holzer, Markus (2009). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2009.04.009">"Language operations with regular expressions of polynomial size"</a>. Theoretical Computer Science. 410 (35): 3281–3289. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2009.04.009">10.1016/j.tcs.2009.04.009</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1176.68105">1176.68105</a>.</cite>.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-02" href="https://en.wikipedia.org/wiki/?title=Circular_shift&oldid=1254892127">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>